package com.example.algorithm.backtrcaking.backrewrite;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/20
 * 组合数
 */
public class ZuHe {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list=new ArrayList<>();
        Deque<Integer> deque=new LinkedList<>();

        backTracking(list,deque,n,k,1);
        return list;
    }

    private void backTracking(List<List<Integer>> list, Deque<Integer> deque, int n, int k, int startIndex) {

        if(deque.size()==k)
        {
            list.add(new ArrayList<>(deque));
            return ;
        }


        /**
         * 这里使用的剪枝的思想，因为n-(k-deque.size())+1之后的数字不够组合，所以使用剪枝，将其不纳入计算当中
         *
         * 我之前的写法是    for(int i=startIndex;i<=n;i++)  这样会多了几步内必要的操作
         */
        for(int i=startIndex;i<=n-(k-deque.size())+1;i++)
        {
            deque.addLast(i);
            backTracking(list, deque, n, k, i+1);
            deque.removeLast();
        }
    }


    public static void main(String[] args) {
        ZuHe zuHe = new ZuHe();
        List<List<Integer>> combine = zuHe.combine(4, 2);
        combine.stream().forEach(System.out::println);
    }
}
